package 数组.middle;

/**
 * @author Lw中
 * @date 2021/9/11 21:47
 */
public class YiBaJiuSi {

    // 1894.找到需要补充粉笔的学生编号

    public static int chalkReplacer(int[] chalk, int k) {
        // 方法一：模拟优化
//        int len = chalk.length;
//        // 因为total有可能会超过32整数的取值范围，需要使用64位进行保存
//        long total = 0;
//        // 计算一轮需要消耗几支粉笔
//        for (int i = 0; i < len; i++) {
//            total += chalk[i];
//        }
//        // 求余数
//        k %= total;
//        int res = -1;
//        for (int i = 0; i < len; i++) {
//            if (chalk[i] > k) {
//                res = i;
//                break;
//            }
//            else k = k - chalk[i];
//        }
//        return res;

        // 方法二：前缀和（当前位置及之前的元素总和） + 二分查找
        // 前缀和数组是一个递增数列便于二分查找
        /**
         * LWZ TODO : 2021/9/11 为什么对前缀和数组进行二分查找可以找出需要添加粉笔的学生
         *
         */
        if (chalk[0] > k) {
            return -1;
        }
        // 获取前缀和数组并判断是否有学生需要添加粉笔
        for (int i = 1; i < chalk.length; i++) {
            chalk[i] += chalk[i - 1];
            if (chalk[i] > k) {
                return i;
            }
        }
        k %= chalk[chalk.length - 1];
        return binarySearch(chalk, k);

    }

    private static int binarySearch(int[] chalk, int target) {
        int low = 0, high = chalk.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (chalk[mid] <= target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] ints = {5, 1, 5};
        int i = chalkReplacer(ints, 22);
        System.out.println(i);
    }

}
